let nums = [1, 3, -1, -1, 0, 5, 3, 6, 7];
let k = 3;

// var maxSlidingWindow = function (nums, k) {
//   const res = [];

//   for (let i = 0; i <= nums.length - k; i++) {
//     const arr = nums.slice(i, k + i);
//     res.push(Math.max(...arr));
//   }

//   return res;
// };

var maxSlidingWindow = function (nums, k) {
  const len = nums.length;
  const res = [];
  const deque = []; // 双端队列，存储元素的下标

  for (let i = 0; i < len; i++) {
    // 移除不在当前窗口内的元素 左出
    if (deque.length > 0 && deque[0] < i - k + 1) {
      deque.shift();
    }

    // 移除队列中比当前元素小的元素
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }

    // 将当前元素添加到队列
    deque.push(i);

    // 当窗口大小达到 k 时，记录当前窗口的最大值
    if (i >= k - 1) {
      res.push(nums[deque[0]]);
    }
  }

  return res;
};

console.log(maxSlidingWindow(nums, k));
